% \documentstyle[epsf,epic,eepic,eepicemu]{article}
\documentclass[a4paper,10pt]{article}
\usepackage[czech, english]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{indentfirst} % ceske odstavce
\usepackage[bookmarks=true, colorlinks=true, breaklinks=true, urlcolor=red, citecolor=blue, linkcolor=blue, unicode=true,]{hyperref}

% \oddsidemargin=-5mm
% \evensidemargin=-5mm\marginparwidth=.08in \marginparsep=.01in
% \marginparpush=5pt\topmargin=-15mm\headheight=12pt
% \headsep=25pt\footheight=12pt \footskip=30pt\textheight=25cm
% \textwidth=17cm\columnsep=2mm
% \columnseprule=1pt\parindent=15pt\parskip=2pt

% definice pro použití v textu
\newcommand\WorkTitle{Semestralní projekt MI-PAR 2010/2011: \\ Úloha TLG: tloušťka grafu}
\newcommand\WorkAuthor{Jakub Podlaha \\ Jan Molnár} % \and nějak neodřádkuje!

% \newcommand{\zadani}[1]{{\color{blue}{Zadání: #1}}}
\newcommand{\zadani}[1]{}
\newcommand{\todo}[1]{{\color{red}{TODO #1}}}

\title{\WorkTitle}
\author{\WorkAuthor}

\begin{document}
\selectlanguage{czech}
\hypersetup{pdftitle={\WorkTitle}, pdfauthor={\WorkAuthor}}

\maketitle

\section{Definice problému}
\subsection{Zadání}
Vytvořte algoritmus pro výpočet tloušťky grafu. Vstupem je ze souboru načtená
matice sousednosti, výstupem tloušťka grafu. Algoritmus vytvořte typu
L-PBB-DFS-D.

L-PBB-DFS-D: prohledávání konečného stavového prostoru do hloubky s odřezáváním horších větví, než s lokálně nejlepším nalezeným řešením.

Podrobné zadání se nachází na \cite{Zadani}.

\subsection{Tloušťka grafu}
Pro zjištění tloušťky grafu musíme projít všechny uzlové permutace grafu. Pro
každou permutaci srovnáme uzly do řady a spojíme je hranami. Dále "řežeme"
mezery mezi jednotlivými uzly a načítáme hrany, které řez protíná. Řez kterým
prochází největší počet hran se nazývá tloušťka permutace. Tloušťka grafu je
pak tloušťka nejmenší z permutací. 

\subsection{Vstupní data}
Vstupem je matice sousednosti, která reprezentuje souvislý neorientovaný neohodnocený graf o n uzlech (zadáno na prvním řádku). \\
Příklad zadání:
\begin{verbatim}
9
001000010
000101001
100101100
011001100
000000001
011100001
001100010
100000100
010011000
\end{verbatim} 


\section{Popis sekvenčního algoritmu}
Sekvenční algoritmus načte zadání, inicializuje proměnné vypočítá tloušťku
grafu ze zadání a po vypsání výsledku uklidí paměť.

Nejprve je načtena matice sousednosti zpracovávaného grafu o \verb|n| uzlech, z
té je určena triviální spodní mez řešení \verb|t|. Poté se vytvoří zásobník, na
který se ukládají jednotlivé stavy výpočtu a začne se se samotným výpočtem.

Permutace grafu se vytvářejí nad polem indexů. Toto pole prohazuje řádky a
sloupečky matice přemapováním indexů. Do tohoto pole se prokládají indexy od 0
do n-1.  Postupně se tedy od nejmenšího (dáno pořadím při načítáni) berou
jednotlivé uzly grafu a vkládají se do všech pozic mezi ostatními již vloženými
uzly grafu.

Většina takto vzniklých permutací je vložena na zásobník, jedna je ale vždy
rozpracovávaná rekurzivně dále. Po přidání uzlu je spočítána aktuální tloušťka
grafu v daném místě. Pokud je vyšší než zatím nejnižší dosažená, výpočet
procházené větve permutací je ukončen a přejde se k další, perspektivnější.
Pokud ještě zbývájí nějaké uzly, jsou přidávány, pokud jde ale o permutaci
délky \verb|n| jde o list grafu permutací, neboli permutaci celého grafu.  Při
jejím měření, v případě lepšího výsledku, než doposud nejnižší tloušťky grafu,
je aktualizováno nejlepší řešení.  Odsekávána jsou také řešení symetrická s již
řešenými případy porovnáváním prvního a posledního indexu koncových permutací.
Tím se ušetří měření poloviny listů tedy $ n! / 2 $ měření. 

\zadani{Popiste problem, ktery vas program resi. Jako vychozi pouzijte text
zadani, ktery rozsirte o presne vymezeni vsech odchylek, ktere jste
vuci zadani behem implementace provedli 
(napr.  upravy heuristicke funkce, organizace zasobniku,
apod.). Zminte i pripadne i takove prvky algoritmu, ktere v zadani
nebyly specifikovany, ale ktere se ukazaly jako dulezite.  Dale
popiste vstupy a vystupy algoritmu (format vstupnich a vystupnich
dat). Uvedte tabulku namerenych casu sekvencniho algoritmu pro ruzne
velka data.}


\section{Popis paralelního algoritmu a jeho implementace v MPI}
Paralelizování přidává do výpočtu několik nových algoritmů. Všechny vycházejí
z \cite{ProgramovaniMPI}. Nejprve je prvním procesorem načteno zadání, poté
všem broadcastem rozeslána velikost grafu, následuje inicializace ostatních
instancí na správnou velikost podle zadané matice sousednosti a na konci
počáteční fáze je broadcastem ještě rozeslána samotná matice sousednosti s
dalšími odvozenými údaji.

Poté je každému procesoru rozeslána množina podzadání a každý z procesorů dále
postupuje, jako v sekvenčním algoritmu, pouze jednou za určitý počet cyklů
zkontroluje, zda mu někdo neposlal zprávu. V případě vyřešení veškeré přidělené
práce procesor pošle žádost o další práci procesoru s nižším indexem a ten mu podmnožinu
své práce přidělí. V případě, že dotazovaný má nanejvýše malé množství práce
(definováno konstantou určující počet zbývajících uzlů do konce rozvoje),
odpoví, že žádnou práci nemá. Procesor se dále dotazuje omezeného počtu dalších
jader. Pokud žádnou práci nedostane stává se \verb|iddle|. 

Pokud se řídící procesor dostane do \verb|iddle| stavu začne se zajímat o to,
jak jsou na tom ostatní procesory. Vyšle token s flagem CanFinnish po směru
číslování procesorů. V případě, že procesory již nemají žádnou práci, nebo
neprobíhá její výměna, oběhne token celé kolečko. Po doběhnutí tokenu řídící
procesor rozešle zprávu o ukončení výpočtu. 

Po dokončení výpočtu je z výsledných dat binární redukcí určen nejlepší
výsledek, který je řídícím procesorem vypsán.

\zadani{Popiste paralelni algoritmus, opet vyjdete ze zadani a presne vymezte
odchylky, zvlaste u algoritmu pro vyvazovani zateze, hledani darce, ci ukonceni
vypoctu.  Popiste a vysvetlete strukturu celkoveho paralelniho algoritmu na
urovni procesuu v MPI a strukturu kodu jednotlivych procesu. Napr. jak je
naimplemtovana smycka pro cinnost procesu v aktivnim stavu i v stavu
necinnosti. Jake jste zvolili konstanty a parametry pro skalovani algoritmu.
Struktura a semantika prikazove radky pro spousteni programu.}


\section{Naměřené výsledky a vyhodnocení}
Výslednou aplikaci jsme pro různé vstupy spustili na svazku STAR na jednom,
dvou, čtyřech, osmi, šestnácti, dvaceti čtyř a třiceti dvou jádrech. Časy jsme
zaznamenaly a celé měření několikrát opakovali a průměrovali, vzhledem k velmi
nízkým odchylkám to ale nebylo moc potřeba, doby výpočtů jsou v podstatě
natolik stabilní, že by se dala použít pro daný případ libovolná naměřená
hodnota.

Porovnání rychlostí sítí Ethernet a InfiniBand vyšlo překvapivě spíše ve
prospěch Ethernetu, buď má nižší inicializační nároky (v implementovaném
algoritmu neprobíhají velké transfery dat), spíše ale usuzujeme na chybu měření
způsobenou nerovnoměrnými výkony jednotlivých přidělených sad procesorů svazku
STAR. S určitou pravděpodobností by se domněnku dalo experimentálně ověřit.

Na obrázku \ref{fig:graf9-3} jsou na levém grafu znázorněny naměřené výsledky pro graf o devíti uzlech s průměrným stupněm uzlu tři. Už z tohoto grafu je vidět, že takto snadné zadání nemá smysl paralelizovat, náklady na paralelizaci jsou mnohem vyšší, než samotná doba výpočtu. V pravé části je umístěn graf reprezentující zrychlení tohoto grafu, i tyto hodnoty vypovídají o zbytečnosti paralelizace.
\begin{figure}[h]
 \centering
 \includegraphics{./graf9-3.png}
 % graf9-3.png: 640x261 pixel, 112dpi, 14.52x5.92 cm, bb=0 0 411 168
 \caption{Naměřené hodnoty a zrychlení extra malého grafu.}
 \label{fig:graf9-3}
\end{figure}

Na obrázku \ref{fig:graf10-7} jsou znázorněny naměřené výsledky pro malý graf o desíti uzlech s průměrným stupněm uzlu sedm. U tohoto grafu je už vidět přínos paralelizace. Zrychlení je lineární.
\begin{figure}[h]
 \centering
 \includegraphics{./graf10-7.png}
 % graf10-7.png: 640x265 pixel, 112dpi, 14.52x6.01 cm, bb=0 0 411 170
 \caption{Naměřené hodnoty a zrychlení malého grafu.}
 \label{fig:graf10-7}
\end{figure}

Na obrázku \ref{fig:graf12-6} jsou znázorněny naměřené výsledky pro větší, ale řidší, graf o dvanácti uzlech s průměrným stupněm šest. Zrychlení je opět lineární.
\begin{figure}[h]
 \centering
 \includegraphics{./graf12-6.png}
 % graf12-6.png: 640x265 pixel, 112dpi, 14.52x6.01 cm, bb=0 0 411 170
 \caption{Naměřené hodnoty a zrychlení většího grafu.}
 \label{fig:graf12-6}
\end{figure}

Na obrázku \ref{fig:graf11-10} jsou znázorněny naměřené výsledky pro velmi hustý graf o jedenácti uzlech s průměrným stupněm deset. Zrychlení je opět lineární.
\begin{figure}[h]
 \centering
 \includegraphics{./graf11-10.png}
 % graf11-10.png: 640x265 pixel, 112dpi, 14.52x6.01 cm, bb=0 0 411 170
 \caption{Naměřené hodnoty a zrychlení hranově zaplněného grafu.}
 \label{fig:graf11-10}
\end{figure}

Algoritmus se pro všechny výše uvedené zadání chová podobně, zrychlení je lineární, efektivnost ale s přibývajícím počtem procesorů mírně klesá.


\zadani{\begin{enumerate}
\item Zvolte tri instance problemu s takovou velikosti vstupnich dat, pro ktere ma sekvencni 
algoritmus casovou slozitost kolem 5, 10 a 15 minut.
Pro mereni cas potrebny na cteni dat z disku a ulozeni na disk neuvazujte a zakomentujte
ladici tisky, logy, zpravy a vystupy.
\item Merte paralelni cas pri pouziti $i=2,\cdot,32$ procesoru na sitich Ethernet a InfiniBand.
%\item Pri mereni kazde instance problemu na dany pocet procesoru spoctete pro vas algoritmus dynamicke delby prace celkovy pocet odeslanych zadosti o praci, prumer na 1 procesor a jejich uspesnost.
%\item Mereni pro dany pocet procesoru a instanci problemu provedte 3x a pouzijte prumerne hodnoty.
\item Z namerenych dat sestavte grafy zrychleni $S(n,p)$. Zjistete, zda a za jakych podminek
doslo k superlinearnimu zrychleni a pokuste se je zduvodnit.
\item Vyhodnodte komunikacni slozitost dynamickeho vyvazovani zateze a posudte
vhodnost vami implementovaneho algoritmu pro hledani darce a deleni zasobniku pri reseni vaseho
problemu. Posudte efektivnost a skalovatelnost algoritmu. Popiste nedostatky
vasi implementace a navrhnete zlepseni.
\item Empiricky stanovte 
granularitu vasi implementace, tj., stupen paralelismu pro danou velikost reseneho
problemu. Stanovte kriteria pro stanoveni mezi, za kterymi jiz neni
ucinne rozkladat vypocet na mensi procesy, protoze by komunikacni
naklady prevazily urychleni paralelnim vypoctem.

\end{enumerate}}


\section{Závěr}
Semestrální práce byla pro nás velikým přínosem, bez praxe, kterou jsme jí získali, bychom si řešení problémů spjatých s paralelizací stěží dokázali představit. Tvrzení platí nejmarkantněji o problematikách dělby práce a ukončování paralelního algoritmu. Nabitou znalost programování v OMPI bereme jako příjemný bonus.

\zadani{Celkove zhodnoceni semestralni prace a zkusenosti ziskanych behem semestru.}


% \section{Literatura}
\bibliographystyle{abbrv}
%bibliographystyle{plain}
%\bibliographystyle{psc}
{
%JZ: 11.12.2008 Kdo chce mit v techto ukazkovych odkazech take odkaz na CSTeX:
\def\CS{$\cal C\kern-0.1667em\lower.5ex\hbox{$\cal S$}\kern-0.075em $}
\bibliography{reference}
}
\appendix

\zadani{\section{Navod pro vkladani grafu a obrazku do Texu}

Nejjednodussi zpusob vytvoreni obrazku je pouzit sunovsky graficky editor xfig,
ze ktrereho lze exportovat latex formaty (v poradi prosty latex, 
latex s macry epic, eepic, eepicemu) a postscript formaty,
uvedene poradi odpovida rustu komplikovanosti obrazku
(postscript umi jakykoliv obrazek, prosta latex macra pouze jednoduche,
epic makra neco mezi, je treba vyzkouset). Nasleduji priklady
pro vsechny pripady. 

Obrazek v postscriptu, vycentrovany a na celou sirku stranky, 
s popisem a cislem. Vsimnete si, jak ridit velikost obrazku.
% \begin{figure}[ht]
% \epsfysize=3cm
% \centerline{\epsfbox{VasObrazek.ps}}
% \caption{Popis vaseho obrazku}
% \label{labelvasehoobrazku}
% \end{figure}

Obrazek pouze vlozeny mezi radky textu, bez popisu a cislovani.\\
% \epsfxsize=1cm
% \rule{0pt}{0pt}\hfill\epsfbox{VasObrazek.ps}\hfill\rule{0pt}{0pt}

Texovske obrazky maji pripony *.latex, *.epic, *.eepic, a *.eepicemu, respective. 
% \begin{figure}[ht]
% \begin{center}
% \input VasObrazek.latex
% \end{center}
% \caption{Popis vaseho obrazku}
% \label{l1}
% \end{figure}
Vypustenim zavorek {\tt figure} dostanete opet pouze ramecek 
v textu bez cisla a popisu. 

Takhle jednoduse muzete poskladat obrazky vedle sebe.
% \begin{center}
% \setlength{\unitlength}{0.1mm}\input VasObrazek.epic
% \hglue 5mm 
% \setlength{\unitlength}{0.15mm}\input VasObrazek.eepic
% \hglue 5mm 
% \setlength{\unitlength}{0.2mm}\input VasObrazek.eepicemu
% \end{center}
% Ridit velikost texovskych obrazku lze prikazem
% \begin{verbatim}
% \setlength{\unitlength}{0.1mm}
% \end{verbatim}
ktere meni meritko rastru obrazku, Tyto prikazy je ale soucasne 
nutne vyhodit ze souboru, ktery xfig vygeneroval.

Pro vytvareni grafu lze pouzit program gnuplot, ktery umi generovat postscriptovy soubor, ktery vlozite
do Texu vyse uvedenym zpusobem.}

\end{document}
